package basic.study.leetcode;

/**
 * @ClassName Mid5
 * @Description 最长回文子串
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/21 23:25
 * @Version 1.0
 */
public class Mid5 {
    class Solution {
        public String longsetPalindrome(String s) {
            int len = s.length();
            String reverse = new StringBuilder(s).reverse().toString();
            int[][] arr = new int[len][len];
            int maxLen = 0;
            int maxEnd = 0;
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    if (s.charAt(i) == reverse.charAt(j)) {
                        if (i == 0 || j == 0) {
                            arr[i][j] = 1;
                        } else {
                            arr[i][j] = arr[i-1][j-1] + 1;
                        }
                    }
                    //验证
                    if (arr[i][j] >maxLen) {
                        int beforeRev = len - j + 1;
                        if (beforeRev + arr[i][j] - 1 == i) {//判断下标是否对应
                            maxLen = arr[i][j];
                            maxEnd = i;
                        }
                    }
                }
            }
            return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
        }
    }
}
